#ifndef _ResultTree_H_
#define _ResultTree_H_

/******************************************************************************

Description:
  ResultTree class. Intended for using in fp-tree like result tree structures.

Author: Tayfun Sen
Website: http://blog.tayfunsen.com
 
 *****************************************************************************/

// Standard libraries.
#include <vector>
#include <iostream>
#include <string>
#include <ext/hash_map>
#include <fstream>
// Boost libraries for serializing.
#include <boost/tokenizer.hpp>
#include <boost/archive/tmpdir.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/serialization/utility.hpp>
#include <boost/serialization/hash_map.hpp>
#include <boost/serialization/map.hpp>
#include <boost/serialization/string.hpp>
#include <boost/mpi.hpp>
// Custom libraries.
#include "shared.hpp"
#include "HeaderInfo.hpp"
#include "Node.hpp"
#include "Prefix.hpp"


using namespace std;
using namespace __gnu_cxx;


class ResultTree {
    public:
        // Root will not hold any value.      
        ResultTree() :root(new Node("root", -1)) {}

        // We need a copy constructor for Tree. Since it is used when passed by
        // value, returned by value etc. This one uses the copy assignment 
        // operator for constructing. See copy-assignment op.
        ResultTree(const ResultTree & t) : root(new Node("root", -1)) {
            *this = t; }

        // Copy assignment operator.
        const ResultTree & operator= (const ResultTree & rhs);

        ~ResultTree() {
            makeEmpty(); }

        void makeEmpty() {
            makeEmpty(root); 
            // Also remove the two level index hash table.
            index.clear();

        }

        int insert(vector<string> *, int count = 1);

        Node * getRoot() const {
            return root; }

        // Used when reducing trees. They are merged using this method.
        void merge(ResultTree &);

        // Used in sub-itemset pruning technique.
        bool subItemsetPruning(Prefix &);
        bool isProperSubset(Node *, vector<string> &);

        int print(string filename);
   
    private:
        friend class boost::serialization::access;
        template<class Archive>
            void serialize(Archive & ar, const unsigned int version) {
                ar & root;
                ar & index;
            }

        int isAbsorbed(Node * node, vector<string> * transaction);

        int insertTransaction(vector<string> * transaction, int count);

        int insertIndexInfo(Node * node);

        int makeEmpty(Node * & t);

        // Duplicate creates a new tree which is the same as the one given as
        // its parameter and returns the root node. The children are also 
        // inserted to the header table. So it does pretty much all the 
        // housekeeping as well.
        Node * duplicate(const Node *);

        void insertSubTree(Node * fromCurrentTree, Node * fromNewTree);

        int printRec(Node * node, vector<string> items, int support = -1);

        //*****************************************
        //************ data ***********************
        // Pointer to the root node.
        Node * root;

        // This index is used extensively in the mining process. Specifically
        // when implementing sub-itemset pruning and during subset checking.
        // It is used to find only closed frequent itemsets.
        hash_map<string, hash_map<int, Node *> *> index;

        // For writing the results to a file (or any stream).
        ofstream outputStream;
        //************ end data *******************
};

#endif

